package com.chengqs.datastructure.stack;

import java.util.LinkedList;

/**
 * 后缀表达式求值
 */
public class E02Leetcode150 {

    /*

        |   |
        | 13|
        | 4 |
        _____

        "4","13","5","/","+"

        - 遇到数字压入栈
        - 遇到运算符, 就从栈弹出两个数字做运算, 将结果压入栈
        - 遍历结束, 栈中剩下的数字就是结果
     */

    public int evalRPN(String[] tokens) {
        LinkedList<Integer> stack = new LinkedList<>();
        for (String t : tokens) {
            switch (t) {
                case "+":
                    Integer b1 = stack.pop();
                    Integer a1 = stack.pop();
                    stack.push(a1 + b1);
                    break;
                case "-":
                    Integer b2 = stack.pop();
                    Integer a2 = stack.pop();
                    stack.push(a2 - b2);
                    break;
                case "*":
                    Integer b3 = stack.pop();
                    Integer a3 = stack.pop();
                    stack.push(a3 * b3);
                    break;
                case "/":
                    Integer b4 = stack.pop();
                    Integer a4 = stack.pop();
                    stack.push(a4 / b4);
                    break;
                default: // 数字
                    stack.push(Integer.parseInt(t));
                    break;
            }
        }
        return stack.pop();
    }
}
